package version2024.medium;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author sunhl
 * @Description: HJ67 24点游戏算法  递归, BigDecimal
 * @Date: created in 2025/1/4 星期六 16:05
 * @Modified By:
 */
public class HJ67_24pointGameAlgorithm {
    // 3 3 8 8 , 适用的解法  (8 / (3 - (8 / 3))) = 24 , 注意用int除会丢失精度(8 / 3 = 2, 8 /(3-2) = 8), 这个case就过不了
    // 7 9 10 9 ,  （9+10）*9/7 结果整数型也是24, 但浮点结果24.428... 这个case应该不通过

    // 用于接收传入的4个整数
    private static BigDecimal[] arr;
    // 用于判断对应序号的整数有没有被使用。
    private static int[] visited;

    // 24的BigDecimal值, 用于后面的比较
    private static BigDecimal de24;

    // 0的BigDecimal值, 用于后面的比较
    private static BigDecimal de0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            arr = new BigDecimal[4];
            visited = new int[4];
            de24 = new BigDecimal(24);
            de0 = new BigDecimal(0);
            // 获取输入的4个整数
            for (int i = 0; i < 4; i++) {
                arr[i] = new BigDecimal(in.nextInt());
            }

            System.out.println(canGet24(0, new BigDecimal(0)));

        }
    }

    // 递归计算24点
    private static boolean canGet24(int cnt, BigDecimal tempres) {
        // 递归终止条件：已经使用了数组四个元素，同时结果为24，满足题意
        // 由于存在除法除不尽的情况, 这里与24比较精度到2位小数
        if (cnt == 4
                && de24.compareTo(tempres.setScale(2, BigDecimal.ROUND_HALF_EVEN)) == 0) {
            return true;
        }

        // 对于还没开始运算的情况，接收的第一个数值直接作为tempres
        if (cnt == 0) {
            for (int i = 0; i < 4; i++) {
                visited[i] = 1;
                if (canGet24(cnt + 1, arr[i])) {
                    return true;
                }
                visited[i] = 0;
            }
            return false;
        }

        // 已经存在一个数参加运算和三个数参加运算, 逻辑是相同的
        if (cnt == 1 || cnt == 3) {
            for (int i = 0; i < 4; i++) {
                // 只有未被使用的数参与后续运算
                if (visited[i] == 0) {
                    visited[i] = 1;
                    // 加和乘, 减计算
                    if (canGet24(cnt + 1, tempres.add(arr[i])) ||
                            canGet24(cnt + 1, tempres.multiply(arr[i]))
                            || canGet24(cnt + 1, tempres.subtract(arr[i])) ||
                            canGet24(cnt + 1, arr[i].subtract(tempres))) {
                        return true;
                    }
                    // 除法计算
                    if (tempres.compareTo(de0) != 0 &&
                            canGet24(cnt + 1, arr[i].divide(tempres, 10, BigDecimal.ROUND_HALF_EVEN))
                            || arr[i].compareTo(de0) != 0 &&
                            canGet24(cnt + 1, tempres.divide(arr[i], 10, BigDecimal.ROUND_HALF_EVEN))) {
                        return true;
                    }
                    visited[i] = 0;
                }

            }

            // 所有情况都试过了，还是没有24出现，返回false
            return false;
        }

        if (cnt == 2) {
            // 对于已经在两个数值参加运算的情况，要考虑两种可能
            // 1.另两个数字参加运算后再和当前结果运算。
            // 剩下两个数值取到a,b中
            BigDecimal a = new BigDecimal(0);
            BigDecimal b = new BigDecimal(0);
            for (int i = 0; i < 4; i++) {
                if (visited[i] == 0) {
                    if (a.compareTo(de0) == 0) {
                        a = arr[i];
                    } else {
                        b = arr[i];
                    }
                }
            }
            // 对所有可能的ab运算结果进行计算, 得到n
            for (BigDecimal n : getAnyRes(a, b)) {
                // 对所有可能的tmpres和n的运算结果进行判断
                for (BigDecimal m : getAnyRes(tempres, n)) {
                    if (m.compareTo(de24) == 0) {
                        return true;
                    }
                }
            }

            //2.当前结果与第三个数值参加运算。
            for (int i = 0; i < 4; i++) {
                if (visited[i] == 0) {
                    visited[i] = 1;
                    // 加和乘, 减计算
                    if (canGet24(cnt + 1, tempres.add(arr[i])) ||
                            canGet24(cnt + 1, tempres.multiply(arr[i]))
                            || canGet24(cnt + 1, tempres.subtract(arr[i])) ||
                            canGet24(cnt + 1, arr[i].subtract(tempres))) {
                        return true;
                    }
                    // 除法计算
                    if (tempres.compareTo(de0) != 0 &&
                            canGet24(cnt + 1, arr[i].divide(tempres, 10, BigDecimal.ROUND_HALF_EVEN))
                            || arr[i].compareTo(de0) != 0 &&
                            canGet24(cnt + 1, tempres.divide(arr[i], 10, BigDecimal.ROUND_HALF_EVEN))) {
                        return true;
                    }
                    visited[i] = 0;
                }
            }

            //所有情况都试过了，还是没有24出现，返回false
            return false;
        }

        return false;
    }

    private static List<BigDecimal> getAnyRes(BigDecimal a, BigDecimal b) {
        List<BigDecimal> res = new ArrayList<>();
        res.add(a.add(b));
        res.add(a.multiply(b));
        res.add(a.subtract(b));
        res.add(b.subtract(a));
        if (a.compareTo(de0) != 0) {
            res.add(b.divide(a, 10, BigDecimal.ROUND_HALF_EVEN));
        }
        if (b.compareTo(de0) != 0) {
            res.add(a.divide(b, 10, BigDecimal.ROUND_HALF_EVEN));
        }

        return res;
    }
}
